package com.zjsru.plan2024.oneday;

import com.zjsru.common.TreeNode;

/**
 * 1367. 二叉树中的链表
 *
 * @Author: cookLee
 * @Date: 2024-12-30
 */
public class IsSubPath {

    /**
     * 主
     * 如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
     * \
     * 输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
     * 输出：true
     * 解释：树中蓝色的节点构成了与链表对应的子路径。
     * \
     * 输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
     * 输出：true
     * \
     * 输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
     * 输出：false
     * 解释：二叉树中不存在一一对应链表的路径。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(8)));
        TreeNode tree = new TreeNode(1, new TreeNode(4,
                new TreeNode(4, null,
                        new TreeNode(2, new TreeNode(2, null,
                                new TreeNode(1, null, new TreeNode(6,
                                        new TreeNode(8, null, null), null))), null)),
                new TreeNode(2, null,
                        new TreeNode(1, null,
                                new TreeNode(3, null, null)))), null);
        IsSubPath isSubPath = new IsSubPath();
        System.out.println(isSubPath.helper(head, tree));
    }

    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) {
            return false;
        }
        return this.helper(head, root) || this.isSubPath(head, root.right) || this.isSubPath(head, root.left);
    }

    private boolean helper(ListNode head, TreeNode node) {
        //全部匹配
        if (head == null) {
            return true;
        }
        //节点为空失败
        if (node == null) {
            return false;
        }
        //当前值与链表节点不相等
        if (head.val != node.val) {
            return false;
        }
        //深度搜索下一层
        return this.helper(head.next, node.left) || this.helper(head.next, node.right);
    }
}
